﻿#define _CRT_SECURE_NO_WARNINGS 1


#include<stdio.h>
//给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
//
//
//
//示例 1:
//
//输入: nums = [1, 2, 3, 4, 5, 6, 7], k = 3
//输出 : [5, 6, 7, 1, 2, 3, 4]
//解释 :
//	向右轮转 1 步 : [7, 1, 2, 3, 4, 5, 6]
//	向右轮转 2 步 : [6, 7, 1, 2, 3, 4, 5]
//	向右轮转 3 步 : [5, 6, 7, 1, 2, 3, 4]
//	示例 2 :
//
//	输入：nums = [-1, -100, 3, 99], k = 2
//	输出：[3, 99, -1, -100]
//	解释 :
//	向右轮转 1 步 : [99, -1, -100, 3]
//	向右轮转 2 步 : [3, 99, -1, -100]
//

//时间换空间做法
//void rotate(int* nums, int numsSize, int k)
//{
//    k %= numsSize;
//    int temp[numsSize];
//    int i = 0;
//    int j = 0;
//    //将后面k个元素放到temp[]前面
//    for (i = numsSize - k; i < numsSize; i++)
//    {
//        temp[j] = nums[i];
//        j++;
//    }
//    //将前面n-k个元素放到temp[]后面
//    for (i = 0; i < numsSize - k; i++)
//    {
//        temp[j] = nums[i];
//        j++;
//    }
//    for (i = 0; i < numsSize; i++)
//    {
//        nums[i] = temp[i];
//    }
//    return 0;
//}


//逆置数组
void reverse(int begin, int end, int* nums)
{
	int i = 0;
	int temp = 0;
	while(begin<end)
	{
		temp = nums[begin];
		nums[begin] = nums[end];
		nums[end] = temp;
		begin++;
		end--;
	}
}
void rotate(int* nums, int numsSize, int k)
{
	k %= numsSize;
	//前numssize-k个元素逆置
	reverse(0, numsSize-k-1, nums);
	//后k个元素逆置
	reverse(numsSize - k, numsSize-1, nums);
	//整体逆置
	reverse(0, numsSize - 1, nums);
}






//
//
//
//
//数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？
//
//注意：本题相对书上原题稍作改动
//
//示例 1：
//
//输入：[3, 0, 1]
//输出：2

//
////异或做法
//int missingNumber(int* nums, int numsSize)
//{
//    int N = numsSize;
//    int i = 0;
//    int ret = 0;
//    for (i = 0; i < N; i++)
//    {
//        ret ^= nums[i];
//
//    }
//    int j = 0;
//    for (j = 0; j <= N; j++)
//    {
//        ret ^= j;
//    }
//    return ret;
//
//}
//
//
//
////求和做法
//int missingNumber(int* nums, int numsSize)
//{
//    int N = numsSize;
//    int x = N * (N + 1) / 2;
//    int i = 0;
//    for (i = 0; i < N; i++)
//    {
//        x -= nums[i];
//    }
//    return x;
//}
